/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-06-05
 * Time: 11:06
 */
public class Solution {
//     分成两部分的动态规划
//     一个 dp 数组记录左边的连乘
//     另一个记录右边的连乘
//     左右的乘积就是结果
    public int[] constructArr(int[] a) {
        int len = a.length;
        int[] ans = new int[len];
        if (len == 0) {
            return ans;
        }
        // 左边的连乘
        int[] dpL = new int[len];
        // 右边的连乘
        int[] dpR = new int[len];
        dpL[0] = a[0];
        dpR[len-1] = a[len-1];
        for (int i = 1;i < len - 1;i++) {
            dpL[i] = dpL[i-1] * a[i];
        }
        for (int i = len-2;i >= 0;i--) {
            dpR[i] = dpR[i+1] * a[i];
        }
        // 左右的乘积就是结果
        ans[0] = dpR[1];
        ans[len-1] = dpL[len-2];
        for (int i = 1;i < len-1;i++) {
            ans[i] = dpL[i-1] * dpR[i+1];
        }
        return ans;
    }
}
